package base.day08;

import java.util.Comparator;
import java.util.PriorityQueue;

/**
 * 描述：
 *      一块金条切成两半，是需要花费和长度数值一样的铜板的。输入一个数组，返回分割的最小代价
 *      哈夫曼数，每次选出最小的两个相加，然后放回到堆中
 * @author hl
 * @version 1.0
 * @date 2020/11/1 15:09
 */
public class LessMoney {
    public static int lessMoney(int[] arr){
        PriorityQueue<Integer> priorityQueue = new PriorityQueue<>(new MinheapComparator());
        for (int i = 0; i < arr.length; i++) {
            priorityQueue.add(arr[i]);
        }
        int res = 0;
        int cur = 0;
        while(priorityQueue.size() > 1){
            cur = priorityQueue.poll() + priorityQueue.poll();
            res += cur;
            priorityQueue.add(cur);
        }
        return res;
    }
    public static class MinheapComparator implements Comparator<Integer> {

        @Override
        public int compare(Integer o1, Integer o2) {
            return o1 - o2; // < 0  o1 < o2  负数
        }

    }

    public static class MaxheapComparator implements Comparator<Integer> {

        @Override
        public int compare(Integer o1, Integer o2) {
            return o2 - o1; // <   o2 < o1
        }

    }
    public static void main(String[] args) {
        // solution
        int[] arr = { 6, 7, 8, 9 };
        System.out.println(lessMoney(arr));

        int[] arrForHeap = { 3, 5, 2, 7, 0, 1, 6, 4 };

        // min heap
        PriorityQueue<Integer> minQ1 = new PriorityQueue<>();
        for (int i = 0; i < arrForHeap.length; i++) {
            minQ1.add(arrForHeap[i]);
        }
        while (!minQ1.isEmpty()) {
            System.out.print(minQ1.poll() + " ");
        }
        System.out.println();

        // min heap use Comparator
        PriorityQueue<Integer> minQ2 = new PriorityQueue<>(new MinheapComparator());
        for (int i = 0; i < arrForHeap.length; i++) {
            minQ2.add(arrForHeap[i]);
        }
        while (!minQ2.isEmpty()) {
            System.out.print(minQ2.poll() + " ");
        }
        System.out.println();

        // max heap use Comparator
        PriorityQueue<Integer> maxQ = new PriorityQueue<>(new MaxheapComparator());
        for (int i = 0; i < arrForHeap.length; i++) {
            maxQ.add(arrForHeap[i]);
        }
        while (!maxQ.isEmpty()) {
            System.out.print(maxQ.poll() + " ");
        }

    }

}
